package MergeSort;
//归并排序
import java.util.Random;

public class Sort {
    //static int number=0;
    public static void main(String[] args) {
        Random random = new Random();
        int[] a = new int[10];
        for (int i = 0; i < a.length; i++) {
            a[i] = random.nextInt(100);
        }
        for (int i : a) {
            System.out.print(i + "   ");
        }
        System.out.println();
        sort01(a,0,a.length-1);
        for(int i=0;i<a.length;i++)
        {
            System.out.print(a[i]+"   ");
        }
    }
    public static void sort01(int []a,int low,int high)
    {
        //int mid,i,j,k;
        if(low>=high) {
            return;
        }
            int mid = (low + high) / 2;
            sort01(a, low, mid);
            sort01(a, mid+1, high);
            merge(a,low,mid,high);
    }
    public static void merge(int []a,int low,int mid,int high)
    {
        int []b=new int[a.length];
        int i = low;
        int j = mid+1;
        int k = low;
//        while (low <= mid || j <= high) {
//            if (j == high || (low <= mid && a[i] <= a[j])) {
//                b[k++] = a[low++];
//            } else {
//                b[k++] = a[j++];
//            }
//
//        }
//        for(k=low;k<high;k++)
//        {
//            a[k]=b[k];
//        }
        while(low <=mid && j <= high) {
            if (a[low] <= a[j])
                b[k++] = a[low++];
            else
                b[k++] = a[j++];
        }
        // 将左边剩余的归并
        while (low <=mid) {
            b[k++] = a[low++];
        }
        // 将右边剩余的归并
        while ( j <= high ) {
            b[k++] = a[j++];
        }
        while(i<=high){
            a[i]=b[i];
            i++;
        }
    }
}
